#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <string.h>

using namespace std;

// 线性探测法
// 增加/插入
// 1、判断是否需要扩容，根据hash因子来判断，一般如果hash因子大于0.75，就需要扩容
//      hash因子 = 填入的元素个数 / hash表长度
// 2、判断是否需要移动元素，如果当前计算的位置已经被占用，就向后移动一位，直到找到一个空位
//      状态：0：从未使用，1：已使用，2：已删除

// 查找
// 1、计算索引值，判断索引值是否越界，判断索引值是否被占用，判断索引对应的值是否为要查找的值
//      如果是，就直接返回
//      如果不是，就向后移动一位，直到找到/越界

// 删除
// 1、先查找
// 2、找到了直接标记为已删除状态

// 不足：
// 1、产生散列冲突，产生堆积，导致查找效率降低，最后劣化为O(n)
// 2、多线程场景下，只能对全局hash表加锁（防止多个线程同时操作时出现覆盖），导致效率降低

enum State {
    EMPTY = 0,
    USED = 1,
    DELETED = 2
};

// 定义桶结构
struct Bucket {
    // 构造函数
    Bucket(int key = -1, State state = EMPTY) {
        this->key = key;
        this->state = state;
    }
    int key;
    State state; // 0：从未使用，1：已使用，2：已删除
};

// 定义哈希表结构
class LinearHashTable {
private:
    // 哈希函数
    // 除留余数法
    int hashcalc(int key)
    {
        return key % tableSize_;
    }
    void resize()
    {
        // 扩容
        for (; primeIdx_ < PRIME_NUM; primeIdx_++)
        {
            if (primes_arr[primeIdx_] > tableSize_)
            {
                break;
            }  
        }

        if (primeIdx_ == PRIME_NUM)
        {
            throw "error: the size is too large, can't expand the hash tabel.";
        }

        tableSize_ = primes_arr[primeIdx_];
        cout << "resize table size to " << tableSize_ << endl;
        Bucket* newTable = new Bucket[tableSize_];
        for (size_t i = 0; i < tableSize_; i++)
        {
            if (table_[i].state == USED)
            {
                int newIndex = hashcalc(table_[i].key);
                newTable[newIndex].key = table_[i].key;
                newTable[newIndex].state = USED;
            }
        }
        delete[] table_;
        table_ = newTable;
    }
public:
    LinearHashTable(int size = primes_arr[0],int bucketusednum = 0,float hashFactor = 0.75)
        : primeIdx_(0)
        , bucketusednum_(bucketusednum)
        , hashFactor_(hashFactor)
    {
        if (size != primes_arr[0])
        {
            for (; primeIdx_ < PRIME_NUM; primeIdx_++)
            {
                if (primes_arr[primeIdx_] >= size)
                {
                    break;
                }  
            }

            if (primeIdx_ == PRIME_NUM)
            {
                throw "error: the size is too large, please use a smaller size.";
            }
        }
        tableSize_ = primes_arr[primeIdx_];
        cout << "create table size : " << tableSize_ << endl;
        table_ = new Bucket[tableSize_];
    }
    ~LinearHashTable()
    {
        delete[] table_;
        table_ = NULL;
    }
    void insert(int key)
    {
        // 判断是否需要扩容
        float loadFactor = bucketusednum_ * 1.0 / tableSize_;
        cout << "loadFactor : " << loadFactor << endl;
        if (loadFactor >= hashFactor_)
        {
            // 扩容
            resize();
        }
        // 计算索引值
        int index = hashcalc(key);
        int k = index;
        // 线性探测法插入
        do
        {
            if (table_[k].state == EMPTY)
            {
                table_[k].key = key;
                table_[k].state = USED;
                bucketusednum_++;
                cout << bucketusednum_ << " : " << key << " insert success" << endl;
                break;
            }
            k = hashcalc(k+1);
        } while (k != index);
    }
    int find(int key)
    {
        // 计算索引值
        int index = hashcalc(key);
        // 线性探测法查找
        int k = index;
        do
        {
            if (table_[k].state == USED && table_[k].key == key)
            {
                return k;
            }
            k = hashcalc(k+1);
        } while (k != index);
        return -1;

    }
    void remove(int key)
    {
        do
        {
            int index = find(key);
            if (index != -1)
            {
                table_[index].state = EMPTY;
                bucketusednum_--;
            }
        } while (find(key) != -1);
    }
private:
    Bucket* table_; // 桶数组
    int tableSize_; // 桶数组长度
    int bucketusednum_; // 已使用的桶个数
    float hashFactor_; // 哈希因子
    int primeIdx_; // 哈希表质数索引
    static const int PRIME_NUM = 28; // 哈希表质数个数
    static int primes_arr[PRIME_NUM]; // 哈希表质数表
};


// 定义质数表
int LinearHashTable::primes_arr[PRIME_NUM] = {3, 7, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 
                                        49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 
                                        6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 
                                        402653189, 805306457, 1610612741};


int main(int argc, const char** argv) {
    LinearHashTable table;
    table.insert(1);
    table.insert(2);
    table.insert(10);
    table.insert(8);

    int n = table.find(10);
    cout << "n : " << n << endl;
    table.remove(10);
    n = table.find(10);
    cout << "n : " << n << endl;

    return 0;
}